package a08_回溯算法;

import java.util.Arrays;

/**
 * <p>
 * a21_解数独复习2
 * </p>
 *
 * @author flyduck
 * @since 2025/4/17
 */
public class a21_解数独复习2 {
    public static void main(String[] args) {
        a21_解数独复习2 test = new a21_解数独复习2();
        char[][] board = new char[][]{{'5','3','.','.','7','.','.','.','.'},{'6','.','.','1','9','5','.','.','.'},{'.','9','8','.','.','.','.','6','.'},{'8','.','.','.','6','.','.','.','3'},{'4','.','.','8','.','3','.','.','1'},{'7','.','.','.','2','.','.','.','6'},{'.','6','.','.','.','.','2','8','.'},{'.','.','.','4','1','9','.','.','5'},{'.','.','.','.','8','.','.','7','9'}};
        test.solveSudoku(board);
        for (char[] chars : board) {
            System.out.println(Arrays.toString(chars));
        }
    }

    public void solveSudoku(char[][] board) {
        traversal(board, 0, 0);
    }

    private boolean traversal(char[][] board,
                           int x,
                           int y){
        if(board[x][y] != '.'){
            if(x == board.length - 1 && y == board.length - 1){
                return true;
            }else if(y == board.length - 1){
                boolean traversal = traversal(board, x + 1, 0);
                if(traversal){
                    return true;
                }else {
                    return false;
                }
            }else {
                boolean traversal = traversal(board, x, y+1);
                if(traversal){
                    return true;
                }else {
                    return false;
                }
            }
        }
        for (int i = 1; i <= 9; i++) {
            char num = (i + "").toCharArray()[0];
            if(isValid(board,x,y,num)){
                board[x][y] = num;
                if(x == board.length - 1 && y == board.length - 1){
                    return true;
                }else if(y == board.length - 1){
                    boolean traversal = traversal(board, x + 1, 0);
                    if(traversal){
                        return true;
                    }
                }else {
                    boolean traversal = traversal(board, x, y+1);
                    if(traversal){
                        return true;
                    }
                }
                board[x][y] = '.';
            }
        }
        return false;
    }

    private boolean isValid(char[][] board, int x, int y,char num) {
        for (int i = 0; i < 9; i++) {
            if (board[i][y] == num) {
                return false;
            }
        }

        for (int j = 0; j < 9; j++) {
            if (board[x][j] == num) {
                return false;
            }
        }

        //找第一个方块的x和y
        for(int i = (x / 3) * 3;i < (x / 3) * 3 + 3;i++){
            for(int j = (y / 3) * 3;j < (y / 3) * 3 + 3;j++){
                if (board[i][j] == num) {
                    return false;
                }
            }
        }


        return true;
    }
}
